package basic.study.leetcode;

/**
 * @ClassName Hard124
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/29 10:03
 * @Version 1.0
 */
public class Hard124 {

    class Solution {
        int maxSum = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            maxGain(root);
            return maxSum;
        }

        private int maxGain(TreeNode root) {
            if (root == null) {
                return 0;
            }

            // 递归计算左右子节点的最大贡献值
            // 只有在最大贡献值大于 0 时，才会选取对应子节点
            int leftGain = Math.max(maxGain(root.left), 0);
            int rightGain = Math.max(maxGain(root.right), 0);

            //节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            int priceNewpath = root.val + leftGain + rightGain;

            //更新答案
            maxSum = Math.max(maxSum, priceNewpath);

            //返回节点的最大贡献值
            return root.val + Math.max(leftGain, rightGain);
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
